package me.mingshan.leetcode;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * https://leetcode.cn/problems/binary-tree-tilt/description/
 *
 * 给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。
 *
 * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
 *
 * 整个树 的坡度就是其所有节点的坡度之和。
 *
 * @author hanjuntao
 * @date 2025/10/3 0003
 */
public class L_563_二叉树的坡度 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);

        root.left = node1;
        root.right = node2;

        System.out.println(findTilt(root));
    }

    /**
     * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。
     * 如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
     *
     * 根据对坡度的描述，如果要计算某个节点的坡度，就必须计算左子树的所有节点之和，和右子树所有节点之和
     *
     * 如何计算某个节点的所有节点之和呢？这个可以使用递归来实现
     *
     * 有了左子树和右子树的节点之和，就可以计算该节点的坡度了；
     *  int abs = Math.abs(leftValue - rightValue);
     *
     *  可以将这个值累加到sum中，这样sum就是整个树的坡度
     *
     *
     * @param root
     * @return
     */
    public static int findTilt(TreeNode root) {
        AtomicInteger sum = new AtomicInteger();

        dfs(root, sum);
        return sum.get();
    }

    /**
     * 递归计算某个节点的所有子节点的和
     *
     * @param root
     * @param sum
     * @return 当前节点的所有子节点的和
     */
    private static int dfs(TreeNode root, AtomicInteger sum) {
        if (root == null) {
            return 0;
        }

        int leftTotalValue = dfs(root.left, sum);
        int rightTotalValue = dfs(root.right, sum);

        int abs = Math.abs(leftTotalValue - rightTotalValue);
        sum.addAndGet(abs);

        return leftTotalValue + rightTotalValue + root.val;
    }
}
